Это нормально чувствовать себя
взволнованным и напряженным за день до олимпиады по программированию. Чтобы
расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения
остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала
Ваши друзья написали последовательность n
целых чисел x1, x2,..., xn. Потом следует k
раундов, на каждом из которых выполняется одна из следующих команд:
·
команда изменения, когда необходимо изменить одно значение в последовательности;
·
команда умножения, когда по заданным значениям i и j необходимо
определить, является ли произведение xi
* xi+1 * ... * xj-1 * xj положительным,
отрицательным или равным нулю.
Так как Вы находитесь в пабе, то
штрафом за неправильный ответ будет употребление дополнительной пинты пива. Вы
беспокоитесь, что это может негативно повлиять на Вас при участии в конкурсе на
следующий день, и у Вас нет желания проверять на корректность теорию пика
Баллмера. К счастью, друзья разрешили Вам пользоваться ноутбуком. Поскольку Вы
больше доверяете Вашим способностям программировать, нежели математике, то было
решено написать программу, которая поможет сыграть в игру.
Вход. Каждый тест состоит из нескольких строк. Первая строка каждого теста
содержит два числа n и k (1 ≤ n, k ≤ 105)
– количество элементов в последовательности и число раундов в игре. Вторая
строка содержит n целых чисел xi – начальные значения
последовательности (-100 ≤ xi
≤ 100 для i = 1, 2,..., n). Каждая из следующих k строк описывает команду, начинающуюся
заглавной буквой 'C' или 'P'. Если это буква 'C', то строка содержит команду
замены, за буквой следуют два числа i
и v, указывающих на то что xi необходимо заменить на v (1 ≤ i ≤ n и -100
≤ v ≤ 100). Если это
буква 'P', то строка задает команду умножения, за буквой следуют два числа i и j
– необходимо вычислить произведение от xi
до xj включительно (1
≤ i ≤ j ≤ n). Каждый тест содержит как минимум одну команду умножения.
Выход. Для каждого теста вывести одну строку, содержащую ответы на все
команды умножения. i-ый символ строки
является результатом i-ой команды
умножения. Если произведение положительно, то вывести символ '+' (плюс); если
произведение отрицательно, то вывести '-' (минус); если произведение равно
нулю, то вывести '0' (ноль).
Пример входа
4 6
-2 6 0 -1
C 1 10
P 1 4
C 3 7
P 2 2
C 4 -5
P 1 4
5 9
1 5 -2 4 3
P 1 2
P 1 5
C 4 -5
P 1 5
P 4 5
C 3 0
P 1 5
C 4 -5
C 4 -5
Пример выхода
0+-
+-+-0
РЕШЕНИЕ
структуры данных – дерево
отрезков
Дерево отрезков храним в векторе
SegTree длины 4*MAX. Входную последовательность xi сохраняем в массив а.
#define MAX 100010
int a[MAX], SegTree[4*MAX];
Построение
дерева отрезков из элементов массива a.
void BuildTree(int *a, int Vertex, int Left,
int Right)
{
if (Left == Right) SegTree[Vertex] = a[Left];
else
{
int Middle = (Left + Right) / 2;
BuildTree(a, 2*Vertex, Left, Middle);
BuildTree(a, 2*Vertex+1, Middle+1, Right);
SegTree[Vertex] = SegTree[2*Vertex]
* SegTree[2*Vertex+1];
}
}
Вершине
v соответствует отрезок [LeftPos; RightPos]. Функция Update присваивает элементу с индексом Position значение NewValue.
void Update(int v, int LeftPos, int
RightPos, int Position, int NewValue)
{
if (LeftPos == RightPos) SegTree[v] = NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
Update (2*v, LeftPos, Middle, Position, NewValue);
else Update (2*v+1, Middle+1, RightPos,
Position, NewValue);
SegTree[v] = SegTree[2*v] * SegTree[2*v+1];
}
}
Вершине
v соответствует отрезок [LeftPos; RightPos]. Функция Query возвращает произведение чисел на отрезке
[Left; Right].
int Query(int v, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left > Right) return
1;
if ((Left == LeftPos) && (Right == RightPos))
return SegTree[v];
int Middle = (LeftPos + RightPos) / 2;
return Query(2*v, LeftPos, Middle, Left,
min(Right,Middle)) *
Query(2*v+1, Middle+1, RightPos, max(Left,Middle+1),Right);
}
Основная
часть программы. Читаем входные данные. Вместо значений xi в массиве а сохраняем только их знаки. sgn – функция
знака числа.
while(scanf("%d %d",&n,&k)
== 2)
{
for(i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
a[i] = sgn(a[i]);
}
По
данным в массиве v строим дерево отрезков.
BuildTree(a,1,1,n);
Последовательно
обрабатываем k запросов.
for(z = 0; z < k; z++)
{
scanf("\n%c",&c);
if (c == 'C')
{
scanf("%d %d\n",&pos,&value);
value = sgn(value);
Update(1,1,n,pos,value);
}
else
{
scanf("%d %d\n",&i,&j);
q = Query(1,1,n,i,j);
if(q == 1) printf("+"); else
if(q == 0) printf("0"); else
printf("-");
}
}
printf("\n");
}